\relax 
\catcode`:\active
\catcode`;\active
\catcode`!\active
\catcode`?\active
\select@language{french}
\@writefile{toc}{\select@language{french}}
\@writefile{lof}{\select@language{french}}
\@writefile{lot}{\select@language{french}}
\@writefile{toc}{\contentsline {extrachapter}{\MakeUppercase  {Dedication}}{ii}}
\@writefile{toc}{\contentsline {extrachapter}{\MakeUppercase  {Acknowledgements}}{iii}}
\@writefile{toc}{\contentsline {extrachapter}{\MakeUppercase  {Abstract}}{iv}}
\@writefile{toc}{\contentsline {extrachapter}{\MakeUppercase  {ABR\'{E}G\'{E}}}{v}}
\@writefile{toc}{\contentsline {extrachapter}{\MakeUppercase  {List of Tables}}{viii}}
\@writefile{toc}{\contentsline {extrachapter}{\MakeUppercase  {List of Figures}}{ix}}
\citation{HanPS11}
\citation{Mic01}
\select@language{english}
\@writefile{toc}{\select@language{english}}
\@writefile{lof}{\select@language{english}}
\@writefile{lot}{\select@language{english}}
\@writefile{toc}{\contentsline {chapter}{\numberline {1}Introduction}{1}}
\@writefile{toc}{\contentsline {section}{\numberline {1.1}Notation}{1}}
\citation{SchE94}
\@writefile{toc}{\contentsline {section}{\numberline {1.2}List of Abbreviations}{2}}
\@writefile{toc}{\contentsline {section}{\numberline {1.3}Ordinary Real Least Squares Problem}{2}}
\newlabel{eq:realLSModel}{{1.1}{2}}
\citation{Bjo96}
\citation{Mic01}
\newlabel{eq:realLSResidual}{{1.2}{3}}
\newlabel{eq:normalEquations}{{1.3}{3}}
\@writefile{toc}{\contentsline {section}{\numberline {1.4}Integer Least Squares Problems}{3}}
\newlabel{eq:ils0}{{1.4}{3}}
\citation{Xu07}
\newlabel{eq:boxCon}{{1.5}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {1.5}Applications}{4}}
\citation{Han11}
\citation{Jan04}
\@writefile{lof}{\contentsline {figure}{\numberline {{1--1}}{\ignorespaces An example of a lattice with two different sets of basis vectors.}}{5}}
\newlabel{fig:latticeBasis}{{{1--1}}{5}}
\citation{HanPS11}
\citation{HanPS11}
\citation{Ku11}
\citation{HanPS11}
\@writefile{toc}{\contentsline {section}{\numberline {1.6}Previous Work}{6}}
\newlabel{sec:prevWork}{{1.6}{6}}
\citation{KorZ73}
\citation{AgrEVZ02}
\citation{LenLL82}
\citation{AgrEVZ02}
\citation{LinMH10}
\citation{WubSJM11}
\citation{NguV10}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.6.1}Reduction Strategies}{7}}
\newlabel{subsec:Reductions}{{1.6.1}{7}}
\citation{XieCB11}
\citation{FosGVW99}
\citation{WubBRKK01}
\citation{SuW05}
\citation{ChaH05}
\citation{SchE94}
\citation{Pho81}
\citation{Kan83}
\citation{MurGDC06}
\citation{XuWZW04}
\citation{FukMU04}
\citation{StuBF07}
\citation{DaiY08}
\citation{MurGDC06}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.6.2}Search Strategies}{9}}
\citation{StoVH08}
\citation{SchFL09}
\citation{ChaH05}
\citation{SuW05}
\citation{SuW05}
\citation{SuW05}
\citation{BreC11}
\@writefile{toc}{\contentsline {section}{\numberline {1.7}Objectives and Contribution}{10}}
\citation{MurGDC06}
\citation{SchE94}
\@writefile{toc}{\contentsline {section}{\numberline {1.8}Outline}{12}}
\citation{SchE94}
\citation{AgrEVZ02}
\@writefile{toc}{\contentsline {chapter}{\numberline {2}Schnorr-Euchner Enumeration}{14}}
\newlabel{chap:SESearch}{{2}{14}}
\newlabel{eq:ils}{{2.1}{14}}
\citation{HasV05}
\newlabel{eq:searchIneq0}{{2.2}{15}}
\newlabel{eq:searchC}{{2.3}{15}}
\newlabel{eq:searchIneq1}{{2.4}{15}}
\newlabel{eq:searchLevelK}{{2.5}{15}}
\@writefile{lof}{\contentsline {figure}{\numberline {{2--1}}{\ignorespaces An example of the search process with solution $x = [-1,3,1]^T$.}}{16}}
\newlabel{fig:treeSearch}{{{2--1}}{16}}
\citation{ChaH05}
\citation{Bab86}
\@writefile{toc}{\contentsline {chapter}{\numberline {3}Reduction Strategies}{19}}
\newlabel{chap:Reduction}{{3}{19}}
\citation{FosGVW99}
\citation{ChaP07}
\citation{ChaH05}
\citation{WubBRKK01}
\@writefile{toc}{\contentsline {section}{\numberline {3.1}BILS Reduction Algorithms}{21}}
\newlabel{sec:BILSReduction}{{3.1}{21}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1.1}Previous Reductions}{21}}
\citation{SuW05}
\citation{ChaH05}
\citation{ChaH05}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1.2}CH Algorithm}{23}}
\newlabel{subsec:CH}{{3.1.2}{23}}
\newlabel{eq:swappedCols}{{3.1}{24}}
\newlabel{eq:givensRotation}{{3.2}{24}}
\newlabel{eq:subDiagEntries}{{3.3}{25}}
\newlabel{eq:xic}{{3.4}{25}}
\newlabel{eq:dic}{{3.5}{25}}
\newlabel{eq:subc}{{3.6}{26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1.3}SW Original Algorithm}{26}}
\newlabel{subsec:SW}{{3.1.3}{26}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces CH Algorithm - Returns $p$, the column permutation vector}}{27}}
\newlabel{alg:CH}{{1}{27}}
\newlabel{l:chg}{{9}{27}}
\citation{SuW05}
\citation{SuW05}
\@writefile{lof}{\contentsline {figure}{\numberline {{3--1}}{\ignorespaces Geometry of the search with two different column ordering.}}{28}}
\newlabel{SEGeometry}{{{3--1}}{28}}
\citation{SuW05}
\citation{SuW05}
\newlabel{eq:xis}{{3.7}{30}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces SW Algorithm - Returns $p$, the column permutation vector}}{31}}
\newlabel{alg:SWOrig}{{2}{31}}
\newlabel{l:swG}{{3}{31}}
\newlabel{l:swx}{{7}{31}}
\newlabel{l:swbx}{{8}{31}}
\newlabel{l:swd}{{9}{31}}
\newlabel{l:swy}{{17}{31}}
\newlabel{l:swg}{{19}{31}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1.4}SW Algorithm Interpretation and Improvements}{32}}
\newlabel{sec:improvedSW}{{3.1.4}{32}}
\newlabel{eq:newDist}{{3.8}{32}}
\citation{Cli64}
\newlabel{eq:gup}{{3.9}{33}}
\newlabel{eq:yup}{{3.10}{33}}
\citation{SuW05}
\newlabel{eq:subs}{{3.11}{34}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1.5}Proof of Equivalence of SW and CH}{35}}
\newlabel{eq:xics}{{3.12}{35}}
\newlabel{eq:disc}{{3.13}{36}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1.6}New Algorithm}{37}}
\newlabel{subsec:newReduction}{{3.1.6}{37}}
\citation{LenLL82}
\@writefile{toc}{\contentsline {section}{\numberline {3.2}Reduction for OILS Problems}{38}}
\newlabel{sec:oilsreduction}{{3.2}{38}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {3}{\ignorespaces New algorithm}}{39}}
\newlabel{alg:NEW}{{3}{39}}
\citation{XieCB11}
\newlabel{eq:LLLConditions1}{{3.14}{40}}
\newlabel{eq:LLLConditions2}{{3.15}{40}}
\newlabel{eq:LLLdiagonal}{{3.16}{40}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2.1}Computing the LLL Reduction}{41}}
\@writefile{toc}{\contentsline {subsubsection}{Integer Gauss Transformations.}{41}}
\newlabel{subsec:IGT}{{3.2.1}{41}}
\citation{WubSJM11}
\@writefile{toc}{\contentsline {subsubsection}{Permutations.}{42}}
\newlabel{subsec:Perm}{{3.2.1}{42}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {4}{\ignorespaces LLL Algorithm - Returns R the LLL reduced upper triangular matrix and Z a product of IGTs and permutations}}{43}}
\newlabel{alg:LLL}{{4}{43}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2.2}New Reduction Algorithm}{43}}
\newlabel{subsec:newOILS}{{3.2.2}{43}}
\citation{XieCB11}
\@writefile{lof}{\contentsline {figure}{\numberline {{3--2}}{\ignorespaces LLL Reduction vs LLL+PERMU. Residual from the Babai points.}}{47}}
\newlabel{fig:LLLvsPermuBabai}{{{3--2}}{47}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2.3}Numerical Experiments}{47}}
\newlabel{sec:ILSReductionResults}{{3.2.3}{47}}
\@writefile{lof}{\contentsline {figure}{\numberline {{3--3}}{\ignorespaces LLL Reduction vs LLL+PERMU vs LLL+BABAI. Average times over 200 runs for various problem sizes and noise levels.}}{48}}
\newlabel{fig:LLLvsPermuvsBabai}{{{3--3}}{48}}
\@writefile{lof}{\contentsline {figure}{\numberline {{3--4}}{\ignorespaces LLL Reduction vs LLL+PERMU vs LLL+BABAI. Search time for 200 runs with some different sizes and noise levels.}}{49}}
\newlabel{fig:spikes}{{{3--4}}{49}}
\@writefile{lot}{\contentsline {table}{\numberline {{3--1}}{\ignorespaces Success Rate (out of 200) for LLL and LLL+PERMU on various problem sizes and levels of noise.}}{50}}
\newlabel{tab:successRates}{{{3--1}}{50}}
\@writefile{lof}{\contentsline {figure}{\numberline {{3--5}}{\ignorespaces LLL Reduction vs LLL + PERMU. Residual from the Babai points on ill conditioned problems.}}{51}}
\newlabel{fig:lllvspermubabaiill}{{{3--5}}{51}}
\@writefile{lof}{\contentsline {figure}{\numberline {{3--6}}{\ignorespaces LLL Reduction vs LLL +PERMU vs LLL + BABAI, average search time on ill conditioned problems.}}{52}}
\newlabel{fig:lllvspermuvsbabaiill}{{{3--6}}{52}}
\@writefile{toc}{\contentsline {chapter}{\numberline {4}Alternate Search Strategies}{53}}
\newlabel{chap:Searches}{{4}{53}}
\newlabel{eq:optimalSearchCond}{{4.1}{53}}
\citation{StoVH08}
\citation{FukMU04}
\citation{XuWZW04}
\citation{StuBF07}
\citation{StuBF07}
\citation{AhoHU83}
\@writefile{toc}{\contentsline {section}{\numberline {4.1}Best First Search}{55}}
\newlabel{sec:BFS}{{4.1}{55}}
\citation{DaiY08}
\citation{StuBF07}
\citation{StuBF07}
\@writefile{toc}{\contentsline {section}{\numberline {4.2}Controlling BFS Memory Usage}{58}}
\newlabel{sec:controlBFS}{{4.2}{58}}
\citation{StuBF07}
\@writefile{toc}{\contentsline {section}{\numberline {4.3}Combining BFS and SE Search}{60}}
\citation{StuBF07}
\citation{StuBF07}
\@writefile{toc}{\contentsline {section}{\numberline {4.4}Numerical Testing Results}{64}}
\newlabel{sub:SearchResults}{{4.4}{64}}
\@writefile{lof}{\contentsline {figure}{\numberline {{4--1}}{\ignorespaces Run time results for the combined search process with varying parameter $\alpha $ on random problems.}}{65}}
\newlabel{fig:searchsurface}{{{4--1}}{65}}
\@writefile{lof}{\contentsline {figure}{\numberline {{4--2}}{\ignorespaces Average run time results for the combined search process with varying parameter $\alpha $ on random problems.}}{66}}
\newlabel{fig:searchAverage}{{{4--2}}{66}}
\@writefile{lof}{\contentsline {figure}{\numberline {{4--3}}{\ignorespaces Run time results for the combined search process on ill conditioned problems with varying parameter $\alpha $.}}{67}}
\newlabel{fig:illConditionedSearch}{{{4--3}}{67}}
\@writefile{lof}{\contentsline {figure}{\numberline {{4--4}}{\ignorespaces Average run time results for the combined search process with varying parameter $\alpha $ on ill conditioned problems.}}{68}}
\newlabel{fig:searchAverageIll}{{{4--4}}{68}}
\@writefile{toc}{\contentsline {chapter}{\numberline {5}Conclusions and Future Work}{69}}
\newlabel{chap:Conclusion}{{5}{69}}
\citation{StuBF07}
\bibdata{../ILS}
\bibcite{AgrEVZ02}{1}
\bibcite{AhoHU83}{2}
\bibcite{SchFL09}{3}
\bibcite{Bab86}{4}
\bibcite{Bjo96}{5}
\bibcite{BreC11}{6}
\bibcite{ChaH05}{7}
\bibcite{ChaP07}{8}
\bibcite{StuBF07}{9}
\bibcite{Cli64}{10}
\bibcite{FosGVW99}{11}
\bibcite{FukMU04}{12}
\bibcite{HanPS11}{13}
\@writefile{toc}{\contentsline {extrachapter}{References}{71}}
\bibcite{Han11}{14}
\bibcite{HasV05}{15}
\bibcite{Jan04}{16}
\bibcite{Kan83}{17}
\bibcite{KorZ73}{18}
\bibcite{Ku11}{19}
\bibcite{LenLL82}{20}
\bibcite{LinMH10}{21}
\bibcite{Mic01}{22}
\bibcite{StoVH08}{23}
\bibcite{MurGDC06}{24}
\bibcite{NguV10}{25}
\bibcite{Pho81}{26}
\bibcite{SchE94}{27}
\bibcite{SuW05}{28}
\bibcite{XuWZW04}{29}
\bibcite{WubBRKK01}{30}
\bibcite{WubSJM11}{31}
\bibcite{XieCB11}{32}
\bibcite{Xu07}{33}
\bibcite{DaiY08}{34}
\bibstyle{plain}
